Computer virtualization is a technique that involves encapsulating a physical computing machine platform into virtual machine(s) executing under control of virtualization software on a hardware computing platform or “host” (collectively referred to as a “virtualized computing system”). A virtual machine (VM) provides virtual hardware abstractions for processor, memory, storage, and the like to a guest operating system (OS) and guest application(s) that run on the guest OS. The virtualization software, also referred to as a “hypervisor,” includes one or more virtual machine monitors (VMMs) to provide execution environment(s) for the virtual machine(s). The hypervisor itself can be an OS having a kernel and user applications that run on the kernel. Thus, a virtualized computing system can include various software components executing on the hardware, including the hypervisor kernel, hypervisor user application(s), guest OS(s), and guest application(s).
Modern hypervisors manage memory using a two-stage translation scheme. A guest OS allocates guest virtual memory to its applications, which is mapped to guest physical memory. The hypervisor allocates guest physical memory among its virtual machines, which is mapped to host physical memory. A guest virtual address is translated to a host physical address using two stages of translation: (1) guest virtual address to guest physical address; and (2) guest physical address to host physical address. Modern central processing units (CPUs) include memory management units (MMUs) and translation lookaside buffers (TLBs) that support two-stage address translation at the hardware level. Each guest OS maintains guest page tables for use with the first address translation stage (“first stage page tables”), and the hypervisor maintains hypervisor page tables for use with the second address translation stage (“second stage page tables”).
Modern hypervisors attempt to optimize second stage page tables in order to reduce TLB pressure, use less memory, reduce faults where possible, and the like. One technique to optimize second stage page tables is to walk the first stage page tables, looking for large mappings of guest virtual addresses to guest physical addresses. Scanning first stage tables, however, is a slow process that involves complex algorithms to reduce VM pauses. Accordingly, it is desirable to provide an efficient technique for scanning guest virtual address spaces in a virtualized computing system.